{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Bits LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转数位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个32位整数 <code>num</code>，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>num</code> = 1775(11011101111<sub>2</sub>)\n",
    "<strong>输出:</strong> 8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>num</code> = 7(0111<sub>2</sub>)\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-bits-lcci](https://leetcode.cn/problems/reverse-bits-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-bits-lcci](https://leetcode.cn/problems/reverse-bits-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['0', '2147483647']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num&1:\n",
    "                cur += 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = cur + 1\n",
    "                cur = 0\n",
    "            num = num>>1\n",
    "            res = max(res, cnt)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0  # 当前位置为止连续1的个数\n",
    "        insert=0  # 在当前位置变成1，往前数连续1的最大个数\n",
    "        res=1  # 保存insert最大值即可\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num >= 0:\n",
    "            bnum = bin(num)[2:]\n",
    "        else:\n",
    "            bnum = bin(num & 0xffffffff)[2:]\n",
    "        if len(bnum) < 32:\n",
    "            bnum = \"0\" + bnum\n",
    "        left_index = 0\n",
    "        right_index = 0\n",
    "        ans = 0\n",
    "        zero_indexes = list()\n",
    "        while right_index < len(bnum):\n",
    "            if bnum[right_index] == '0':\n",
    "                zero_indexes.append(right_index)\n",
    "            if len(zero_indexes) > 1:\n",
    "                ans = max(ans, right_index - left_index)\n",
    "                left_index = zero_indexes.pop(0) + 1\n",
    "            right_index += 1\n",
    "            if right_index == len(bnum):\n",
    "                ans = max(ans, right_index - left_index)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 思路: 目标长串中只能包含一个0 \n",
    "        # 从低位到高度遍历\n",
    "        #   遇到1, 则当前连续1长串长度 +1\n",
    "        #   遇到0, 则当前连续1长度长度 = 当前索引 - 上次遇到0的索引\n",
    "\n",
    "        #   8   4     \n",
    "        # 11011101111\n",
    "\n",
    "        cur = 0\n",
    "        rs = 0\n",
    "        last0 = -1  # 上次遇到0的位置\n",
    "        for i in range(32):\n",
    "            # 判断第i位是否为1\n",
    "            if num & (1 << i) != 0:\n",
    "                # 如果为1, 当前连续1的个数++\n",
    "                cur += 1\n",
    "            else:\n",
    "                rs = max(rs, cur)\n",
    "                # 如果为0\n",
    "                cur = i - last0\n",
    "                last0 = i\n",
    "        rs = max(rs, cur)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # print(num)\n",
    "        # print(bin(num))\n",
    "        num=bin(num & 0xffffffff)[2:]\n",
    "        # print(num)\n",
    "\n",
    "        num=\"0\"*(32-len(num))+num\n",
    "        index=0\n",
    "        maxlen=0\n",
    "\n",
    "        while index<len(num):\n",
    "            nowlen=0\n",
    "\n",
    "            if num[index]==\"1\":\n",
    "                while index<len(num) and num[index]==\"1\":\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "\n",
    "                if index<len(num):\n",
    "                    last=index+1\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "                    while index<len(num) and num[index]==\"1\":\n",
    "                        nowlen+=1\n",
    "                        index+=1\n",
    "                    index=last\n",
    "\n",
    "            else:\n",
    "                nowlen+=1\n",
    "                index+=1\n",
    "                last=index\n",
    "                while index<len(num) and num[index]==\"1\":\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "                index=last\n",
    "\n",
    "            maxlen=max(maxlen,nowlen)\n",
    "            \n",
    "\n",
    "        return maxlen\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        length = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                length += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = length + 1\n",
    "                length = 0\n",
    "            \n",
    "            res = max(res, insert)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num += 2**32\n",
    "        bits = []\n",
    "        temp = num\n",
    "        while temp != 0:\n",
    "            bits.append(temp % 2)\n",
    "            temp //= 2\n",
    "        print(bin(num))\n",
    "        max1 = 1\n",
    "        prev1, current1, num0 = 0, 0, 0\n",
    "        for i in range(len(bits)):\n",
    "            if bits[i] == 1:\n",
    "                current1 += 1\n",
    "                temp_len = current1 + 1\n",
    "                if num0 <= 1:\n",
    "                    temp_len += prev1\n",
    "                max1 = max(max1, temp_len)\n",
    "            elif i > 0 and bits[i - 1] == 1:\n",
    "                num0 = 1\n",
    "                prev1 = current1\n",
    "                current1 = 0\n",
    "            else:\n",
    "                num0 += 1\n",
    "        return min(32, max1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 思路: 目标长串中只能包含一个0 \n",
    "        # 从低位到高度遍历\n",
    "        #   遇到1, 则当前连续1长串长度 +1\n",
    "        #   遇到0, 则当前连续1长度长度 = 当前索引 - 上次遇到0的索引\n",
    "\n",
    "        #   8   4     \n",
    "        # 11011101111\n",
    "\n",
    "        cur = 0\n",
    "        rs = 0\n",
    "        last0 = -1  # 上次遇到0的位置\n",
    "        for i in range(32):\n",
    "            # 判断第i位是否为1\n",
    "            if num & (1 << i) != 0:\n",
    "                # 如果为1, 当前连续1的个数++\n",
    "                cur += 1\n",
    "            else:\n",
    "                # 如果为0\n",
    "                cur = i - last0\n",
    "                last0 = i\n",
    "            rs = max(rs, cur)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        c=r=max1=0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                c+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r=c+1\n",
    "                c=0\n",
    "            max1=max(max1,r)\n",
    "        return max1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num<0:\n",
    "            num=int(num+math.pow(2,32))\n",
    "        w= list(bin(num)[2:])\n",
    "        t=[0]\n",
    "        for i in range(len(w)):\n",
    "            if  ascii('0')<= ascii(w[i])<=ascii('9'):\n",
    "                t.append(int(w[i]))\n",
    "        r=[0 for i in range(len(t))]\n",
    "        temp=[0 for i in range(len(t))]\n",
    "        temp[0]=1\n",
    "        r[0]=0\n",
    "        q=0\n",
    "        for i in range(1,len(t)):\n",
    "            if  t[i]==0:\n",
    "                j=i-1\n",
    "                while  True:\n",
    "                    if t[j]==0 or j==0:\n",
    "                        break\n",
    "                    j=j-1\n",
    "                temp[i]=i-j\n",
    "            else:\n",
    "                temp[i]=temp[i-1]+1\n",
    "            r[i]=max(temp[i],r[i-1])\n",
    "            if r[i]>q:\n",
    "                q=r[i]\n",
    "        if q>32:\n",
    "            q=32\n",
    "        return q\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**31 + 2**31 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = zeros[2] - zeros[0] - 1\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0Xffffffff\n",
    "        l = bin(num)[2:]\n",
    "        t = []\n",
    "        for c in l:\n",
    "            if len(t)==0:\n",
    "                t.append([c, 1])\n",
    "            else:\n",
    "                if t[-1][0] == c:\n",
    "                    t[-1][1] += 1\n",
    "                else:\n",
    "                    t.append([c, 1])\n",
    "        #print(t)\n",
    "\n",
    "        ret = 1\n",
    "        for i in range(len(t)):\n",
    "            if t[i][0] == '1':\n",
    "                ret = max(ret, t[i][1] + 1)\n",
    "            \n",
    "                if i<len(t)-2 and t[i+1][1] == 1:\n",
    "                    ret = max(ret, t[i][1] + t[i+2][1]+1)\n",
    "        return min(ret, 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        dp = [0] * 2\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                dp[0] += 1\n",
    "                dp[1] += 1\n",
    "            else:\n",
    "                dp[1] = dp[0] + 1\n",
    "                dp[0] = 0\n",
    "            res = max(res, *dp)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        count = count1 =maxcount1 =0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                count+=1\n",
    "                count1+=1\n",
    "            else:\n",
    "                count1=count+1\n",
    "                count=0\n",
    "            maxcount1=max(maxcount1,count1)\n",
    "        return maxcount1\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=0\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0xffffffff\n",
    "        l = num.bit_length()\n",
    "\n",
    "        r = [0]\n",
    "\n",
    "        # print(l)\n",
    "        for i in range(1,l):\n",
    "            if not num&1:\n",
    "                r.append(i)\n",
    "            num = num>>1\n",
    "        r.append(l+1)\n",
    "\n",
    "        # print(r)\n",
    "\n",
    "        for i in range(len(r)-1, 0, -1):\n",
    "            r[i] = r[i]-r[i-1]-1\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            r[i] += (r[i+1]+1)\n",
    "\n",
    "\n",
    "        # print(r)\n",
    "        return min(max(r), 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, insert)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num==0 or num==1:return 1\n",
    "        val = []\n",
    "        tmp = 0\n",
    "        for i in range(32):\n",
    "            if (num>>i)&1==1:\n",
    "                if tmp>=0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    val.append(tmp)\n",
    "                    tmp=1\n",
    "            else:\n",
    "                if tmp>0:\n",
    "                    val.append(tmp)\n",
    "                    tmp = -1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "        val.append(tmp)\n",
    "        sta = 1 if val[0]<0 else 0\n",
    "        res = val[sta]\n",
    "        n = len(val)\n",
    "        if n==1:return val[0]\n",
    "        for i in range(sta,n,2):\n",
    "            re=0\n",
    "            if i+2<n and val[i+1]==-1:\n",
    "                re += val[i+2]\n",
    "            re += val[i]+1\n",
    "            res = max(res,re)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        x = bin(num & 0xffffffff)[2:].split(\"0\")\n",
    "        n = len(x)\n",
    "        print(x)\n",
    "        if x:\n",
    "            res = len(x[0]) + 1\n",
    "        else:\n",
    "            res = 1\n",
    "        for i in range(n - 1):\n",
    "            res = max(res, len(x[i]) + len(x[i + 1]) + 1)\n",
    "        if res > 32:\n",
    "            return 32\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0xffffffff\n",
    "        \n",
    "        l = num.bit_length()\n",
    "\n",
    "        r = [0]\n",
    "\n",
    "        # print(l)\n",
    "        p = 0\n",
    "        for i in range(1,l):\n",
    "            if not num&1:\n",
    "                r.append(i-p-1)\n",
    "                p = i\n",
    "            num = num>>1\n",
    "        r.append(l-p)\n",
    "\n",
    "        # print(r)\n",
    "\n",
    "        # for i in range(len(r)-1, 0, -1):\n",
    "        #     r[i] = r[i]-r[i-1]-1\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            r[i] += (r[i+1]+1)\n",
    "\n",
    "\n",
    "        # print(r)\n",
    "        return min(max(r), 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0 # 当前位置为止连续1的个数\n",
    "        insert=0 # 变1之后，当前位置为止连续1的个数\n",
    "        res=1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i): # num的第i位为1\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else: # num的第i位为0\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0: # 处理负数\n",
    "            num = pow(2,32) - abs(num)\n",
    "        length = list(map(len,bin(num)[2:].ljust(32,'0').split('0'))) # 将num转为二进制，并以单个字符'0'分隔字符串,然后得出列表中每个字符串的长度,ljust用来前补'0'\n",
    "        return length[0] if len(length)==1 else max(length[i]+length[i+1] for i in range(len(length)-1))+1 # length长度为1说明32位二进制全为1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "\n",
    "        pre, cur = 0,0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                res = max(res, pre+cur)\n",
    "                pre = cur+1\n",
    "                cur = 0\n",
    "        res = max(res, pre+cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur, ins, ans = 0, 0, 0\n",
    "        \n",
    "        for i in range(32):\n",
    "            if num & (1<<i) != 0:\n",
    "                cur += 1\n",
    "                ins += 1\n",
    "            else:\n",
    "                ins = cur + 1\n",
    "                cur = 0\n",
    "            ans = max(ans, ins)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0  # 当前位置为止连续1的个数\n",
    "        insert=0  # 在当前位置变成1，往前数连续1的最大个数\n",
    "        res=1  # 保存insert最大值即可\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        count = count1 =maxcount1 =0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                count+=1\n",
    "                count1+=1\n",
    "            else:\n",
    "                count1=count+1\n",
    "                count=0\n",
    "            if maxcount1<count1:maxcount1=count1\n",
    "        return maxcount1\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        ans = 1\n",
    "        for i in range(32):\n",
    "            if num & 1 == 1:\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            num = num >> 1\n",
    "            ans = max(ans, insert)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 0xffffffff + num + 1\n",
    "        binstr = bin(num)[2:]\n",
    "        binstr = '0' * (32 - len(binstr)) + binstr\n",
    "        idx = [-1, ]\n",
    "        for i, num in enumerate(binstr):\n",
    "            if num == '0':\n",
    "                idx.append(i)\n",
    "        idx.append(len(binstr))\n",
    "        if len(idx) == 2:\n",
    "            return 32\n",
    "        res = 0\n",
    "        for i in range(2, len(idx)):\n",
    "            res = max(res, idx[i] - idx[i-2])\n",
    "        return res - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**32 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = zeros[2] - zeros[0] - 1\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res='{:032b}'.format(num)\n",
    "        if(num < 0):\n",
    "            num = num&0xFFFFFFFF\n",
    "            res = (bin(num))[2:]\n",
    "        print(res)\n",
    "        print(len(res))\n",
    "        dp=[]\n",
    "        temp=0\n",
    "        for x in res:\n",
    "            if x=='0':\n",
    "                dp.append(temp)\n",
    "                temp=0\n",
    "            elif x=='1':\n",
    "                temp+=1\n",
    "        dp.append(temp)\n",
    "        temp=0\n",
    "        print(dp)\n",
    "        if len(dp)==1:\n",
    "            return min(dp[0]+1,32)\n",
    "        for x in range(1,len(dp)):\n",
    "            temp=max(temp,dp[x-1]+dp[x]+1)\n",
    "        return min(32,temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        \n",
    "        a = 0\n",
    "        if num < 0:\n",
    "            a = num\n",
    "            num = -num\n",
    "\n",
    "        bnum = bin(num)[2:]\n",
    "        if a < 0:\n",
    "            while len(bnum) % 4 != 0:\n",
    "                bnum = '0' + bnum\n",
    "                \n",
    "            lb = []\n",
    "            for i in bnum:\n",
    "                if i == '1':\n",
    "                    lb.append('0')\n",
    "                else:\n",
    "                    lb.append('1')\n",
    "   \n",
    "            \n",
    "            rlb = lb[::-1]\n",
    "            rn = len(rlb)\n",
    "    \n",
    "            t = \"\"\n",
    "            for i in range(rn):\n",
    "             \n",
    "                if rlb[i] == '0':\n",
    "                    t += '1'\n",
    "                    t = t + \"\".join(rlb[i + 1:])\n",
    "                    break\n",
    "                else:\n",
    "                    t += '0'\n",
    "            bnum = t\n",
    "            bnum = '1' * (32 - len(bnum)) + bnum[::-1]\n",
    "\n",
    "        res = []\n",
    "        c1, c2 = 0, 0\n",
    "        for i in range(len(bnum)):\n",
    "            if bnum[i] == '0':\n",
    "                c1 += 1\n",
    "                res.append(i)\n",
    "            else:\n",
    "                c2 += 1\n",
    "\n",
    "        if c1 == 0:\n",
    "            return c2 + 1\n",
    "        elif c1 == 1:\n",
    "            return c2 + 1\n",
    "        elif c1 == 2:\n",
    "            return res[1]\n",
    "        else:\n",
    "            ans = res[1]\n",
    "            for j in range(2, len(res)):\n",
    "                ans = max(ans, res[j] - res[j - 2] - 1)\n",
    "            ans = max(ans, len(bnum) - res[-2] -1)\n",
    "            return min(32,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        def count_bit(n:str):\n",
    "            max_n = 0\n",
    "            count = 0\n",
    "            for c in n:\n",
    "                if c == '1':\n",
    "                    count += 1\n",
    "                else:\n",
    "                    max_n = max(max_n, count)\n",
    "                    count = 0\n",
    "            max_n = max(max_n, count)\n",
    "            return max_n\n",
    "        \n",
    "        if num < 0:\n",
    "            for i in range(32):\n",
    "                num ^= 1 << i\n",
    "            num += 1\n",
    "\n",
    "        s = '0' + bin(num)[2:]\n",
    "        zero_pos = []\n",
    "        for i,c in enumerate(s):\n",
    "            if c == '0':\n",
    "                zero_pos.append(i)\n",
    "        \n",
    "        max_n = 0\n",
    "        for i in zero_pos:\n",
    "            max_n = max(max_n, count_bit(s[:i] + '1' + s[i+1:]))\n",
    "            \n",
    "        return max_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**32 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = 0\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur, pre = 0, 0\n",
    "        ans = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, cur + pre)\n",
    "                cur, pre = 0, cur + 1\n",
    "        ans = max(ans, cur + pre)\n",
    "        return ans\n",
    "\n",
    "        # pre, cur =0, 0\n",
    "        # res = 1\n",
    "        # for i in range(32):\n",
    "        #     if num & (1<<i):\n",
    "        #         cur+=1\n",
    "        #     else:\n",
    "        #         res=max(res, pre+cur)\n",
    "        #         pre = cur +1\n",
    "        #         cur = 0\n",
    "        # res=max(res, pre+cur)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        c = 0\n",
    "        insert = 0\n",
    "        r = 1\n",
    "        for i in range(32):\n",
    "            if num &(1<<i):\n",
    "                c += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = c + 1\n",
    "                c = 0\n",
    "            r = max(r,insert)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=1\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, pre)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        ans = pre = cur = 0\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, pre + cur)\n",
    "                pre = cur + 1\n",
    "                cur = 0\n",
    "        ans = max(ans, pre + cur)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        curr = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                curr += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = curr + 1\n",
    "                curr = 0\n",
    "            res = max(res, insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num==0 or num==1:return 1\n",
    "        val = []\n",
    "        tmp = 0\n",
    "        for i in range(32):\n",
    "            if (num>>i)&1==1:\n",
    "                if tmp>=0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    val.append(tmp)\n",
    "                    tmp=1\n",
    "            else:\n",
    "                if tmp>0:\n",
    "                    val.append(tmp)\n",
    "                    tmp = -1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "        val.append(tmp)\n",
    "        sta = 1 if val[0]<0 else 0\n",
    "        res = val[sta]\n",
    "        n = len(val)\n",
    "        if n==1:return val[0]\n",
    "        for i in range(sta,n,2):\n",
    "            re=0\n",
    "            if i+2<n and val[i+1]==-1:\n",
    "                re += val[i+2]\n",
    "            re += val[i]+1\n",
    "            res = max(res,re)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = abs(num)\n",
    "            for i in range(32, -1, -1):\n",
    "                if num >> i & 1 == 0:\n",
    "                    num |= 1 << i\n",
    "                else: num ^= 1 << i\n",
    "            num += 1\n",
    "        left = [0] * 32\n",
    "        right = [0] * 32\n",
    "        for i in range(32):\n",
    "            if num >> i & 1: left[i] += left[i - 1] + 1\n",
    "            else: left[i] = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            if num >> i & 1: right[i] += right[(i + 1) % 32] + 1\n",
    "            else: right[i] = 0\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num >> i & 1 == 0:\n",
    "                a = 0 if i - 1 < 0 else left[i - 1]\n",
    "                b = 0 if i + 1 == 32 else right[i + 1]\n",
    "                res = max(res, a + b + 1)\n",
    "        return max(res, max(left), max(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 需要注意这里是补码\n",
    "        if num<0:\n",
    "            num = bin(num & 0xffffffff)[2:]\n",
    "        else:\n",
    "            num = bin(num)[2:]\n",
    "            num = '0'*(32-len(num))+num\n",
    "        num = [int(i) for i in num]\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k<0:\n",
    "                return 0\n",
    "            if i==0:\n",
    "                return int(k==1 or num[0]==1)\n",
    "            if num[i]==1:\n",
    "                return dp(i-1, k)+1\n",
    "            else:\n",
    "                return dp(i-1, k-1)+k\n",
    "        res = 0\n",
    "        for i in range(len(num)):\n",
    "            res = max(res, dp(i, 1))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        num_bin = self.getBin(num)\n",
    "        # 思路 对二进制列表进行分割，分隔符为0\n",
    "        # 对剩余多个1的数组，只需考虑连续的两个和最大，并加一即是最后结果\n",
    "        num_spl = num_bin.split(\"0\")\n",
    "        max_len = 0\n",
    "        for i in range(len(num_spl) - 1):\n",
    "                max_len = max(max_len,len(num_spl[i])+len(num_spl[i+1]))\n",
    "        return max_len + 1\n",
    "\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "\n",
    "            注意为什么这里需要用32位呢，因为需要考虑负数\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # cur, pre = 0, 0\n",
    "        # ans = 0\n",
    "        # while num:\n",
    "        #     if num % 2 == 0:\n",
    "        #         ans = max(ans, cur + pre + 1)\n",
    "        #         cur, pre = 0, cur\n",
    "        #     else:\n",
    "        #         cur += 1\n",
    "        #     num = num >> 1\n",
    "        # ans = max(ans, cur + pre + 1)\n",
    "        # return ans\n",
    "        pre, cur =0, 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "            else:\n",
    "                res=max(res, pre+cur)\n",
    "                pre = cur +1\n",
    "                cur = 0\n",
    "        res=max(res, pre+cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        if max_length == 0:\n",
    "            max_length = len(q)\n",
    "        else:\n",
    "            if cnt == 1 and res[-1] == 1:\n",
    "                max_length = max(max_length, len(q))\n",
    "            else:\n",
    "                max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        \n",
    "        a = 0\n",
    "        if num < 0:\n",
    "            a = num\n",
    "            num = -num\n",
    "\n",
    "        bnum = bin(num)[2:]\n",
    "        if a < 0:\n",
    "            while len(bnum) % 4 != 0:\n",
    "                bnum = '0' + bnum\n",
    "                \n",
    "            lb = []\n",
    "            for i in bnum:\n",
    "                if i == '1':\n",
    "                    lb.append('0')\n",
    "                else:\n",
    "                    lb.append('1')\n",
    "   \n",
    "            \n",
    "            rlb = lb[::-1]\n",
    "            rn = len(rlb)\n",
    "    \n",
    "            t = \"\"\n",
    "            for i in range(rn):\n",
    "             \n",
    "                if rlb[i] == '0':\n",
    "                    t += '1'\n",
    "                    t = t + \"\".join(rlb[i + 1:])\n",
    "                    break\n",
    "                else:\n",
    "                    t += '0'\n",
    "            bnum = t\n",
    "            bnum = '1' * (32 - len(bnum)) + bnum[::-1]\n",
    "\n",
    "        res = []\n",
    "        c1, c2 = 0, 0\n",
    "        for i in range(len(bnum)):\n",
    "            if bnum[i] == '0':\n",
    "                c1 += 1\n",
    "                res.append(i)\n",
    "            else:\n",
    "                c2 += 1\n",
    "\n",
    "        if c1 == 0:\n",
    "            return c2 + 1\n",
    "        elif c1 == 1:\n",
    "            return c2 + 1\n",
    "        elif c1 == 2:\n",
    "            return res[1]\n",
    "        else:\n",
    "            ans = res[1]\n",
    "            for j in range(2, len(res)):\n",
    "                ans = max(ans, res[j] - res[j - 2] - 1)\n",
    "            ans = max(ans, len(bnum) - res[-2] -1)\n",
    "            return min(32,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        if max_length == 0:\n",
    "            max_length = len(q)\n",
    "        else:\n",
    "            max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for _ in range(32):\n",
    "            if num & 1 == 1:\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, insert)\n",
    "            num >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "      \n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        m = 0\n",
    "        s = '0' + bin(num)[2:] if num > 0 else bin(num & 0xffffffff)[2:]\n",
    "        dp = [0] * len(s)\n",
    "\n",
    "        def dfs(dp: List, index: int, s: str, c: bool):\n",
    "            nonlocal m\n",
    "            if index == len(s):\n",
    "                return\n",
    "            if s[index] == '1':\n",
    "                dp[index] = dp[index - 1] + 1 if index > 0 else 1\n",
    "                m = max(m, dp[index])\n",
    "                dfs(dp, index + 1, s, c)\n",
    "            else:\n",
    "                if not c:\n",
    "                    dp[index] = 0\n",
    "                    dfs(dp, index + 1, s, c)\n",
    "                else:\n",
    "                    dp[index] = 0\n",
    "                    dfs(dp, index + 1, s, True)\n",
    "                    # 这个策略影响的是之后的dp值，所以删去\n",
    "                    for i in range(index + 1, len(dp)):\n",
    "                        dp[i] = 0\n",
    "                    temp = s[:index] + '1' + s[index + 1:]\n",
    "                    dp[index] = dp[index - 1] + 1 if index > 0 else 1\n",
    "                    m = max(m, dp[index])\n",
    "                    dfs(dp, index + 1, temp, False)\n",
    "                    for i in range(index + 1, len(dp)):\n",
    "                        dp[i] = 0\n",
    "\n",
    "        dfs(dp, 0, s, True)\n",
    "        return m\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
